00100		OPTIMIZING THE HUECKEL OPERATOR
00200	
00300	
00400	We seek to choose settings for the Hueckel operator which will
00500	optimize its performance in the sense of requiring the minimum edge height
00600	for 50% detection, while keeping a chosen level of false positives (say
00700	1%), spurious edge candidates with zero signal.  The techniques will
00800	work equally well for other operators and provides a good way of comparison
00900	and optimization.
01000	
01100	We consider only random camera noise.  Surface imperfections are
01200	part of the signal, and will be dealt with later.  The camera noise is
01300	adequately modelled with a gaussian.  The dependence of standard deviation
01400	on signal is a characteristic of the device.  For a vidicon, the noise
01500	is preamp noise, independent of signal.  A linear scale is appropriate for
01600	the vidicon, giving a constant error.  For an image dissector operated in
01700	the mode of requiring a constant photon count, the error is proportional
01800	to the signal; a logarithmic scale gives a constant error.
01900	
02000	The assumptions allow us to calculate analytically the behavior of any
02100	operator.  The Hueckel operator is sufficiently complicated to discourage
02200	analytic calculation.  We have made up fake data using a gaussian random
02300	number generator to obtain artificial edges in various orientations and
02400	step heights, including no step.
02500	
02600	The first step is to determine 1% and 5% limits of the cutoff variables
02700	from fake data with no signal.  These are the cutoff limits set by
02800	false positives.  
02900	For the Hueckel operator, they are conf and diff.  In terms of the signal
03000	squared, s0sq, and noise-squared, n0sq, they are:
03100		diff=s0sq;
03200		conf=sqrt(s0sq/(s0sq+n0sq));  ie the cosine of signal
03300	The second phase of evaluation is to determine the minimum edge signal
03400	which achieves 50% or more detection at the 1% and 5% limits.  Here we
03500	must take enough samples to get a good approximation to these limits.
03600		conf	diff  min edge
03700		.95	1.250	.825
03800		.90	1.350	.70
03900		.85	1.350	.65
04000		.80	1.400	.67
04100		.75	1.400	.67
04200	Values of diff are given in terms of the squared error and values of
04300	the minimum edge are in units of the error.
04400	The last values can be estimated independently.  Since the conf
04500	cutoff has no effect for values below .85, the requirement is that
04600	diff be above the corresponding diff cutoff.  We can evaluate the
04700	mean value of diff by a simulation with no noise.  That value checks
04800	well with the values above.
04900	We note that the conf cutoff has almost no utility, and that the optimum
05000	setting is for conf about .85.
05100	
05200	With the values determined for diff, conf, and the minimum step, we
05300	can calculate the standard deviation of angle and position
05400	of detected edges at various values
05500	of edge height.
05600	This is useful for determining colinearity, angle and position errors
05700	of straight line made from edge vectors, etc, particularly for extrapolation
05800	at vertices.
05900	
06000	A final evaluation is the sensitivity to smooth shading.  Although Hueckel
06100	has said that the operator is insensitive to gradients, a glance at
06200	the analytic form indicates that it basically relies on the slope, or
06300	gradient.  Smooth shading is quite common, and it is the experience
06400	of many of us that the Hueckel operator does turn up spurious edge points
06500	on the surface of curved objects, or where there are reflections.
06550	The same problem limits  the utility of intensity countours and
06575	thresholding techniques.
06600	We are evaluating that sensitivity.
06700	
06800	We can measure the camera noise by one of two methods:
06900		by putting a uniform scene (white paper, defocus camera)
07000		in front of the camera and evaluating
07100		the sum of (x(i+1)-x(i))↑2=2nε↑2
07200	where ε is the standard deviation.  Or we can take the histogram of
07300		(x(i+1)-x(i)) 
07400		for actual scenes.  If we take the 63% limits of the histogram,
07500		we will have an approximation to 2.8ε.  We should not take
07600	the standard deviation from the variance of values, since edges will
07700	affect the sum of squares a great deal, while if edge points are few,
07800	they should not affect local histograms very much.
07900	
08000	It is possible to eliminate undesired sensitivity to smooth shading
08100	by several methods, most of which are not useful.
08200	The second derivatives and third derivatives have more noise than the
08300	gradient.  Subtracting the linear part of the signal over the support
08400	of an operator is a terribly bad method of eliminating smooth gradients.
08500	With the Hueckel operator that would eliminate nearly all the signal.
08600	The problem with that is that the linear approximation is over too small
08700	a support.  What we want is to determine the linear part over a much larger
08800	domain.  Lateral inhibition does this, although it is not immediately apparent.
08900	The biological system uses lateral inhibition for the same purpose as it
09000	was used in my edge operator at MIT.  There is a difficulty with satellites
09100	which will be discussed in a moment.  An elegant solution is the Retinex
09200	operation, by Horn, from Land.  This uses lateral inhibition followed by
09300	the inverse.
09400	
09500	The problem posed to motivate the retinex operation is:
09600	determine the reflectivities of objects, even when the illumination has
09700	shading.  Put another way, illumination varies smoothly, while reflectivities
09800	vary discontinuously at boundaries.  Eliminate the smooth shading.  This can
09900	be done by taking the           Laplacian, thresholding it, and taking
10000	the inverse.   Thus, all the slopes are now turned into plateaus.
10100	The only problem with the operation is that we do not know a speedy
10200	implementation of the inverse.
     

00100	Tests of Hueckel operator
00200	1.  optimal detection tests
00300	2.  local verification is quite inexpensive and is very good for linking
00400		to be followed by a more powerful process for eliminating false
00500		links.
00600	System with Hueckel operator
00700		these mods would increase sensitivity and eliminate the
00800		effects of constant gradients
00900	a. lateral inhibition
01000	b. apply operator
01100	c. local verification and extension
01200		this accomplishes noise reduction and linking of edge fragments
01300	d. eliminating parasite psuedo-edges from the lateral inhibition
     

00100	evaluation of the edge operator
00200		simulate signal on an 8x8 neighborhood
00300		sigma=50.0
00400		conf	diff for .01 false pos	  diff for .05 false pos
00500		.95	411.6				150. (68.8 step)
00600		.90					1166. (step 46.9)
00700		.85					2044. (step 40.6)
     

00100	AN OBVIOUS PROBLEM WITH EDGE FINDERS OCCURS NEAR CORNERS.
00200	AN EDGE FINDER DESIGNED FOR ISOLATED EDGES HAS BIG PROBLEMS
00300	NEAR CORNERS AND HAS SOME OF MANY POSSIBLE FAULTS.  THESE
00400	INCLUDE:
00500		EXTENSION PAST CORNERS
00600		DEFORMATION OF EDGES AT CORNERS
00700		CUTTING OFF EDGES AT CORNERS
00800	
00900	POSSIBLE CURES:
01000		TREAT THIN LINES AS ANOTHER PRIMITIVE, AND
01100			BY SOME COMPLEX PROCESS, MATCH THE TWO MERGED
01200			EDGES WITH THE TERMINATING CORNER
01300		CHOOSE THE BEST DIRECTION TO AVOID INTERFERENCE OF
01400			EDGES AND PROCEED WITHOUT REGARD FOR CORNERS
01500		FIT A CORNER TEMPLATE
01600	
01700		GET HIGHER RESOLUTION AS BY MY SCHEME
     

00100		LOCALIZATION CAN BE DONE IN SEVERAL WAYS.  WE 
00200	WANT NOW TO DISCUSS PREFERENCE AMONG THESE SCHEMES.
00300		1  MAXIMUM OF GRADIENT
00400		THIS WORKS IF THE STEP IS SHARP COMPARED TO THE
00500		INTERVAL OF INTEGRATION.  OTHERWISE, THE RESULT
00600		IS A BROAD FLAT PLATEAU, AND THE MAX OF THE GRADIENT
00700		IS NOT WELL DEFINED, LOCALIZATION IS POOR
00800	
00900		2  MAXIMUM OF CORRELATION GRADIENT
01000		THIS IS ESSENTIALLY THE SAME AS THE GRADIENT, AND
01100		THE SAME REMARKS APPLY
01200	
01300		3  CENTROID OF THE GRADIENT
01400		THIS IS NEARLY EQUIVALENT TO THE CUTOFF AT THE 
01500		VALUE MIDWAY BETWEEN THE TWO EXTREMES.  WHEN THE STEP
01600		IS NARROW, IT TENDS TOWARD THE MAXIMUM OF THE GRADIENT,
01700		AND WHEN THE STEP IS WIDE, IT REMAINS NEAR THE CENTER
01800		OF THE INTERVAL.
01900	
     

00100		Visual processing has progressed more slowly 
00200	than we had hoped.  Our scene description routines currently 
00300	are weak at recognizing boundaries in visual scenes.
00400	One attitude is that it is impossible to do better without
00500	elaborate use of context.  Another is that it is unnecessary
00600	to do better, because very sophisticated and elaborate
00700	use of context will suffice for problems such as have been
00800	attempted.  Whether it is possible to improve
00900	finding of boundaries is a question which can be answeredλd
01000	analytically at some later time when the probe
01100	is better understood.  
01200	At present, facilities and ideas for context are quite pri
01300	primitive and improved boundary detection would lessen theλ
01400	burden on these techniques of using context.
01500		the primary problems in recognizing boundaries
01600	are not really trivial:
01700	
01800	
01900	
02000	
     

00100		1.  W
00200	
00300	
00400		1. We must detect a variety of boundary types.  Discontinuities
00500		appear not only as steps, but as delta functions and slope
00600		discontinuities and combinations of these.  Two treatments have
00700		attempted to enumerate the types of features [hHerskovits,
00800		Griffith].  An operator which looks only for steps would miss
00900		thin lines on a surface.
01000	
01100		2.  
01200	
01300		2.  We must detect a second-derivative like function at 
01400		boundaries, because large constant gradients are very common
01500		with curved surfaces or where there are strong reflections,
01600		as with any stack of blocks.  Consequently, gradient operators
01700		become confused and identify an entire region as edge points.
01800		This is also a problem for operators which fit a step unless the
01900		support is quite large, because there is little difference between
02000		the chi-squared fit of a small step or equivalent constant gradient
02100		(where small step means of the order of the noise in intensity).
02200	
02300		3.
02400		Localization of a discontinuity within the support of the operator
02500		is necessary, because an operator averages over a broad area of 
02600		support.  The value of the operator exceeds cutoff over a range
02700		of position and angle.  
02800		The properties of the localization are not useually considered
02900		at all; taking a maximum is a usual procedure.
03000	
03100		4.  The resolution of small spatial features (or nearby parallel
03200		lines should be near the sensor resolution.  `ltimate resolution
03300		is limited by contrast; with high contrast we can resolve the 
03400		full camera resolution.  Lower contrast requires larger support.
03500		For a human body, many small features on the face are important
03600		for recognition. An intermediate standard of resolution would 
03700		be to detect long thin features with high resolution.
03800	
03900		5.  Global organization of line segments is an integral part
04000		of the analysis of boundary finding.  A local operator generates
04100		line segments which are locally significant, according to its
04200		short-sighted view.  The sensitivtiy of an overall process depends
04300		strongly on how the line segments are turned into lines.  Line
04400		segments from a local operator can be regarded as local hypotheses.  
04500		On a slightly more global scale of organization, these hypotheses
04600		predict nearby intensity values and imply condition on nearby
04700		line segments to be connected.  
04800		The strongest conditions are continuity in intensity and direction. 
04900	e
05000	
05100		
05200		6.  Self-normalization for noise.  Detector noise can be estimated
05300		from a simple model of the detector and its state of operation.	
05400		Thresholds can be calculated simply for detection in the presence
05500		of only Gaussian detector noise of known amplitude.  
05600		In interesting cases, the surfaces are far from homogeneous and
05700		the surface irregularities at a micro scale can be regarded as 
05800		another population of noise, ie too small to have spatial
05900		continuity.  The detection process should be able to be relatively
06000		insensitive to surface noise far in excess of the detector noise.
06100		
06200		7. Sensitivity must be good enough to find many of the boundaries.
06300		Some discussions of sensitivity assume that sensitivity can be
06400		arbitrarily increased by lowering thresholds.  We define sensitivity
06500		as the minimum signal detectable with reasonable probability
06600		(say 50%) for a given noise level (1%, for example).
06700		The overall sensitivity of a process depends not only on the 
06800		sensitivity of a local operator, but also on the subsequent 
06900		organization fo those line segments.  We can determine sensitivity
07000		of local operators by analysis.  Although we don't have a formalism
07100		for choice of an optimum technique, (largely because we have
07200		no adequately precise formalism for defining the conditions for 
07300		optimality) we can look at a well-defined process and make accurate
07400		analytic estimates of its sensitivity.
07500	
07600	
07700	
07800	
07900		We are primarily interested in techniques which will function
08000	with curved objects with fairly uniform surfaces.  We cannot yet handle
08100	much texture, although a reasonable amount can be simply ignored by
08200	strong continuity requirements on organization of edges.
08300	
08400		In what follows, a good model for  noise is that there are two
08500	populations, detector noise and surface blemishes.  Detector noise has
08600	has known spectrum, while surface blemishes may be arbitrary, but have 
08700	infrequent (1%)
     

00100		We discuss some previous techniques for boundary detection
00200		in view of the requirements we have stated.  We begin with
00300	a discussion of local operators and later compare methods of organization.
00400	We later discuss some techniques which improve performance according
00500	to those standards and describe implementations of those techniques.
00600	We discuss error calculations in detail in an appendix.
00700	l.  Gradient operators:
00800		The examples of these operators (Robert's cross [Roberts],
00900	Sobel's operator [Pingle), and coincidence predicates [Binford])
01000	are defined over a small support, 2x2 or 3x3.  Their sensitivity is
01100	inadequate, but even with this low sensitivity, in one of the 
01200	experiments, reflections often caused such large gradients that 
01300	whole faces were seen as full of edge points.  Clearly there is no gain
01400	in using gradient operators with larger support, since their
01500	utility is limited by undesirable sensitivity to constant slopes.
01600	
01700	2.  Second-derivative and third-derivative operators
01800	Herskovits has used second and third derivative operators
01900	to detect step, slope, and delta function discontinuities
02000	in edge verification.  The global organization used enabled
02100	high sensitivity.  Since these operators are insensitive to
02200	constant slopes, the area of support was made large to 
02300	enhance sensitivity, at the expense of resolution of small
02400	features and crowded areas.  The system could handle a considerable
02500	amount of texture.
02600	
02700	
02800	3.  Operators which fit a step.
02900	Hueckel [Hueckel) fits a step function to a domain by parameterizing
03000	a step position and orientation in terms of low-order Fourier 
03100	components.  A goodness of fit is calculated.  The claim is that
03200	the low-frequencies contain the signal and the high frequencies 
03300	contain noise.  At an edge, there is considerable high frequency
03400	signal, and to the extent that it is filtered out, sensitivity 
03500	suffers, and undesirable sensitivity to constant gradients is
03600	emphasized by smearing the distinction.  In our own work, discussed
03700	later, using an operator which fit a step exactly, we encountered
03800	serious problems with reflections and with curved surfaces.
03900	A qualitative evaluation of the claim for low-frequency filtering
04000	is to visually inspect the results of low-pass and high-pass
04100	filtering.  High pass filtering leaves an image almost as good
04200	visually as unprocessed, and in some cases of limited dynamic
04300	range of the recording medium, gives enhancement.  Low pass filtering
04400	severely degrades an image visually.
04500	
04600	4.  Template Operators
04700	Griffith [Griffith] has implemented a scheme using a zoo of about 
04800	10 templates which are correlated with the video signal at points
04900	along a scan line.  The quality of fit is tested and a bbest fit is taken
05000	as a candidate if the correlated signal is above threshold.
     

00100	
00200	TO FIT CURVES TO BOUNDARIES IN THE PLANE:
00300		USE A TWO STAGE SCHEME
00400	
00500		FIRST, TAKE PROJECTIONS AT A FEW ANGLES, FIND
00600		LOCAL EXTREMA BY AN ARRAY (ONE-DIMENSIONAL)
00700		, A PDL IS ALL THAT IS NECESSARY,
00800		WHICH IS LABELLED BY POINTS PASSING OVER.
00900		AN EXTREMUM CAN BE INVESTIGATED BY LOCAL APPROX
01000		OR BY CALCULATION OF THE DIFFERENCE IN ARC LENGTH
01100		AND SAGITTA BETWEEN THE TWO POINTS.  
01200		FOR AN EXTREMUM WHICH IS ALSO A CORNER, THE EXTREMUM
01300		IS STABLE UNDER ROTATIONS (THE FORWARD AND BACKWARD
01400		TANGENTS ARE AT 180 DEGREES FOR SMOOTH CURVES; THE
01500		EXTREMUM IS STABLE FOR A RANGE OF ANGLES BETWEEN
01600		TANF-TANB AND PI.)
01700	
01800		SMALL ANGLE CORNERS WILL BE MISSED BY THIS PROCESS.
01900		HOWEVER, WE CAN USE A SECOND STAGE PROCEDURE WHICH
02000		HAS ALREADY BEEN USED FOR STRAIGHT LINE SEGMENTATION.
02100		THAT PROCEDURE IS TO PROJECT AT ANGLES AROUND THE
02200		THE DIRECTION OF THE LINE BETWEEN ENDPOINTS.  
02300		THE EXTREMA CAN BE TESTED FOR DISCONTINUITY.
02400